1. Field of the Invention
This invention relates generally to the field of data processing, and more particularly to the arbitration of simultaneous service requests. Specifically, the invention relates to a computer interconnect coupler which arbitrates the transmission of addressed data packets among various data processing devices.
2. Description of the Related Art
A conventional digital computer system comprises at least a memory, an input-output device, and a data processor. The memory stores information in addressable storage locations. This information includes data and instructions for processing the data, including commands and responses. The data processor transfers information to and from the memory, interprets the incoming information as either data or instructions, and processes the data in accordance with the instructions. The input-output device also communicates with the memory in order to store input data and output processed data.
A small computer system typically includes a central processing unit, memory, an input-output unit, and a power supply mounted together in a cabinet. The cabinet is built around a frame having a rack or "card cage" defining parallelspaced slots for receiving printed circuit boards including the central processing unit, memory, and input-output unit. The interior edge portions of the circuit boards include terminals which mate with connections on a "back plane" of the card cage. The "back plane" has a number of parallel conductors or buses which interconnect the boards, connect the boards to the power supply, and connect the input/output unit to a number of input/output ports. The buses convey addresses and data, control and status signals, and power and ground. The input/output ports typically include a port for a console terminal, and at least one port for a high-speed input-output device or mass memory such as a floppy disc drive, a tape drive, a high-speed printer, or a hard disc drive.
Advances in circuit technology have made it practical to use additional data processors dedicated to serving respective memory or input/output devices. Therefore, in the cabinet for a typical central processing unit, there is likely to be found a first data processor used for numerical computations, and a second data processor used for controlling the central memory, for example, for formatting or buffering input-output data in one portion of the memory while numerical computations are being performed on data in another portion of the memory. Moreover, the input-output or mass memory devices external to the cabinet for the central processing unit typically have at least one data processing unit or "server" for buffering data and for controlling the devices in response to high-level commands from a central processor.
In recent years, a need has arisen for computation and data storage capabilities exceeding those provided by a few central processing units. For special applications, such as large-scale simulation, these data processing needs can only be met by large computers having a number of central processors and memory linked together by address, data, and control buses. For general applications, however, it is more economical to construct computer networks wherein a number of conventional central processing units, input-output devices, and mass memory devices are located at different positions and are interconnected to communicate with each other. Typically the central processing units share one or more mass memory units to access and update a common data base.
Although there are numerous information transfer schemes which could be used for communication among the data processing devices in a network, the typical method is to use a shared communications resource (i.e., channel or bus) which interconnects the various elements. In general, a transmission between two devices over a shared bus requires two steps, since each device has the capability of originating a transmission at the same time. The first step is for the initiating unit to obtain control of the bus for some more or less defined interval. The second step is for the initiating unit to transfer information over the bus.
Obtaining control of the bus requires arbitration to select a particular one of the devices desiring bus access. There are two general approaches to arbitration, which are known as "central" arbitration and "distributed" arbitration. In central arbitration, a single, central priority circuit or device receives all requests for bus access and determines which requesting device at any given time should be accorded the greatest priority and allowed to use the bus. Once that device is selected, it is allowed to control the bus and effect the transfer. By contrast, in distributed arbitration, each unit connected to the bus is assigned a specific priority and each unit individually determines whether it has sufficient priority to obtain control of the bus when it desires to do so. If a unit of higher priority simultaneously seeks bus access, a device of lower priority must wait until some later time when it is the highest priority requester.
A distributed arbitration scheme known as "carrier-sense multiple access with collision detection" (CSMA/CD) permits a number of devices to communicate over a single bit-serial line such as a coaxial cable. Each device includes circuitry for monitoring the channel and indicating whenever two devices are transmitting at the same time. When a device which is transmitting detects that another device is transmitting at the same time, the two devices stop transmitting. Both then retry transmission after the channel is clear.
One kind of conventional coaxial cable serial data communication network is known as "Ethernet." The Ethernet operates at up to 10 megabits per second and typically provides up to 1,023 addressable devices on a segment of the network. The Ethernet is especially useful for linking a large number of timesharing terminals to a central processing unit.
High speed information transfer over a shared bus between separate data processing devices involves additional requirements such as rapid synchronization, isolation, and highly reliable data transfer. Special hardware and communications protocols have been devised to meet these requirements.
Due to variations in propagation velocity, it is relatively impractical to transmit data at high speed in parallel fashion over a multi-line bus connecting distant data processing devices. Also, due to the requirement of fast synchronization, it is undesirable to transmit data in a non-return-to-zero format. Preferably one or more serial data streams are transmitted in a modulated or self-clocking format. The preferred format is Manchester encoding, as described in Stewart U.S. Pat. No. 4,592,072 and Stewart et al. U.S. Pat. No. 4,450,572, which are herein incorporated by reference. Manchester encoding also has the advantage of removing the DC and lower-frequency components of the data signal, so that the encoded signal will readily pass through simple isolation transformers.
Reliable data transmission is especially important in computer networks having a shared data base. In such a case, any interruption in the updating of a data base must be detected by the updating central processor in order to correct the errors which may occur, and also the interruption must be detected by the memory server in order to prevent other central processors from using partially changed or obsolete data.
A communications protocol for achieving reliable high-speed data transmission is disclosed in Strecker et al. U.S. Pat. 4,560,985 which is herein incorporated by reference. Arbitration is preferably performed on a rotating or "round robin" basis so that on the average, each data processing device on a shared channel has an equal chance of obtaining access. The absence of a carrier on the channel indicates that a data processing device may attempt to obtain access. An arbitration timer indicates transmission failure when the carrier fails to be absent within a certain timeout period. Collisions of data packets or other transmission errors are detected by an error detecting code such as a cyclic redundancy check.
When a data processing device correctly receives a data packet, it immediately acknowledges receipt of that packet by return transmission of an acknowledgment code. If the data packet was processed upon receipt, a positive acknowledgment code (ACK) is returned. If the information packet was correctly received but could not be processed, a negative acknowledgment code (NAK) is returned. In a typical case, the negative acknowledgment code signals that the received data packet could not be processed upon receipt due to unavailability of a buffer, and therefore the received data packet was discarded.
Arbitration for transmission of the acknowledgment code is not required; the code is transmitted as soon as the carrier of the received data packet is removed from the transmission channel. Transmission of the acknowledgment code must be completed within a certain time period. After this time period, the other data processing devices may begin to arbitrate and transmit additional data packets.
If a data processing device fails to receive an acknowledgment code immediately after transmission of a data packet, retransmission should be attempted consecutively up to a predetermined number of times. Similarly, if a negative acknowledgment code is received, retransmission should be attempted for a somewhat greater number of times. In order to break deadlocks, a pseudorandum or "coin flip" decision should be made when the data packet is available for retransmission. If the result of the decision is TRUE, retransmission is attempted. If the result of the decision is FALSE, the data processing device waits for a certain delay time interval and repeats the decision process. The delay time interval, for example, should be at least the minimum amount of time for all of the data processing devices to access the channel; in other words, if all of the data processing units were attempting retransmission, there should be some time available for the transmission of data packets and retransmission of acknowledgment codes, aside from the time required to detect collisions and arbitrate.
Alternative transmission channels are required to assure high availability and reliability in communication. As disclosed in Strecker et al. U.S. Pat. 4,490,785, herein incorporated by reference, the selection of alternative channels should be made on a random basis, with all channels being equally probable. The task of channel selection should be done by an interface circuit which is shared among the alternative channels.
For coupling data processing devices which use the abovementioned communications techniques, a cluster of the devices are typically connected directly to a pair of centrally located signal transformers having a separate winding for each device. Each transformer provides a shared channel interconnecting the data processing devices, and the central location of the transformers assures a minimal transmission delay. Such a computer interconnect coupler, however, has a somewhat limited connectivity due to the limited transmission bandwidth or throughput of the shared channel. If additional data processing devices were to be interconnected to a central transformer, each processor would be guaranteed a proportionally smaller share of the transmission bandwidth. Therefore, to interconnect additional data processing units, it is necessary to add additional channels so that transmission may occur simultaneously over a number of channels. In this case, however, each data processing unit must be provided with additional ports and interface circuitry. Moreover, the ports and interface circuitry cannot merely be duplicated since additional means are required for selecting a particular port for transmission, and obtaining incoming data from a particular one of the ports. It is especially undesirable to make such modifications on existing computer equipment.